Cho số nguyên dương n, hai số nguyên: a,b được gọi là đồng dư theo mô-đun n nếu chúng có cùng số dư khi chia cho n. Điều này tương đương với hiệu a-b chia hết cho n.

Ký hiệu:

a ≡ b ( mod n ) {\displaystyle a\equiv b{\pmod {n}}\,}

Ví dụ:

11 ≡ 5 ( mod 3 ) {\displaystyle 11\equiv 5{\pmod {3}}\,}

Vì 11 và 5 khi chia cho 3 đều cho số dư là 2:

11: 3 = 3 (dư 2)

5: 3 = 1 (dư 2)

tính chất:<3

Ngoài các tính chất của một quan hệ tương đương (phản xạ, đối xứng, bắc cầu), phép đồng dư còn có thêm các tính chất sau:Có thể cộng, trừ, nhân và nâng lên lũy thừa các đồng dư thức có cùng một mô-đun, cụ thể.Nếu ta có:

a 1 ≡ a 2 ( mod n ) {\displaystyle a_{1}\equiv a_{2}{\pmod {n}}\,} b 1 ≡ b 2 ( mod n ) {\displaystyle b_{1}\equiv b_{2}{\pmod {n}}\,}

Thì ta có:

• ( a 1 + b 1 ) ≡ ( a 2 + b 2 ) ( mod n ) {\displaystyle (a_{1}+b_{1})\equiv (a_{2}+b_{2}){\pmod {n}}\,}
• ( a 1 − b 1 ) ≡ ( a 2 − b 2 ) ( mod n ) {\displaystyle (a_{1}-b_{1})\equiv (a_{2}-b_{2}){\pmod {n}}\,}
• ( a 1 b 1 ) ≡ ( a 2 b 2 ) ( mod n ) . {\displaystyle (a_{1}b_{1})\equiv (a_{2}b_{2}){\pmod {n}}.\,}
• a 1 k ≡ a 2 k ( mod n ) {\displaystyle a_{1}^{k}\equiv a_{2}^{k}{\pmod {n}}\,} , với k nguyên dương.

Luật giản ước

Nếu ( a 1 ∗ b ) ≡ ( a 2 ∗ b ) ( mod n ) {\displaystyle (a_{1}*b)\equiv (a_{2}*b){\pmod {n}}\,} và (b,n)=1 (b,n nguyên tố cùng nhau)thì a 1 ≡ a 2 ( mod n ) {\displaystyle a_{1}\equiv a_{2}{\pmod {n}}\,}